Single Number

Posted on |

问题描述（难度简单-136）

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

XOR（异或）

如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

方法一：一边遍历Map

一遍遍历保留只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
public int singleNumber(int[] nums) {
        Map<Integer,Integer> map= new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i])==null){
                map.put(nums[i],1);
            }else {
                map.remove(nums[i]);
            }
        }
        return (Integer) map.keySet().toArray()[0];
    }

方法二：XOR

first , we have to know the bitwise XOR in java:

  • 0 ^ N = N
  • N ^ N = 0

So….. if N is the single number:

N1 ^ N1 ^ N2 ^ N2 ^…………..^ Nx ^ Nx ^ N= (N1^N1) ^ (N2^N2) ^…………..^ (Nx^Nx) ^ N= 0 ^ 0 ^ ……….^ 0 ^ N

= N

1
2
3
4
5
6
7
8
9
10
public int singleNumber(int[] nums) {
    int ans =0;
    
    int len = nums.length;
    for(int i=0;i!=len;i++)
        ans ^= nums[i];
    
    return ans;
    
}

总结

采用XOR（异或）的方式，相同的数字都相互抵消了，最后留下单一的不同的数字。也就是方法二的精髓。